package nowcoder.all;

import java.util.ArrayList;
import java.util.Arrays;

public class NC92 {

    public static void main(String[] args) {

        String s1 = "1A2B3C";
        String s2 = "A1B2C3";
        System.out.println(LCS(s1,s2));
    }

    public static String LCS (String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        int[][] dp = new int[len1+1][len2+1]; //dp[i][j]代表s1[0,i)和s2[0,j)的最长公共子序列
        //那么dp[i][j]={dp[i-1][j-1]+s1[i]==s2[j]?1:0,dp[i-1][j],dp[i][j-1]}
        for (int i = 1; i <= len1; i++) {
            char c1 = s1.charAt(i-1);
            for (int j = 1; j <= len2; j++) {
                char c2 = s2.charAt(j-1);
                //只有c1==c2时，dp[i][j]才可能相比dp[i-1][j-1]增加1，dp[i-1][j-1]相比dp[i-1][j]顶多差1
                //所以增加后dp[i][j]不用再和dp[i-1][j]相比
                if(c1==c2) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
            }
        }
        //还原dp
        char[] res = new char[dp[len1][len2]];
        int i = len1, j = len2, count = res.length-1;
        while (count>=0){
            while (j>0&&dp[i][j]==dp[i][j-1]) j--;
            while (i>0&&dp[i][j]==dp[i-1][j]) i--;
            res[count--] = s1.charAt(i-1);
            i--;j--;
        }

        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        return res.length==0?"-1":new String(res);
    }
}
